//给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
//输出：6
//解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 
// 
//
// 示例 2： 
//
// 
//输入：height = [4,2,0,3,2,5]
//输出：9
// 
//
// 
//
// 提示： 
//
// 
// n == height.length 
// 1 <= n <= 2 * 10⁴ 
// 0 <= height[i] <= 10⁵ 
// 
// Related Topics 栈 数组 双指针 动态规划 单调栈 👍 2946 👎 0

package leetcode.editor.cn;



import java.util.Deque;
import java.util.LinkedList;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution42 {

    /**
     * 法三：单调栈法
     */
    public int trap(int[] height) {
        int sum = 0;
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        for(int i = 1; i < height.length; i++){
            if(height[i] < height[stack.peek()]){
                stack.push(i);
            } else if(height[i] == height[stack.peek()]){
                stack.pop();
                stack.push(i);
            } else {
                while(!stack.isEmpty() && height[i] > height[stack.peek()]){ //这里是while
                    int mid = stack.peek();
                    stack.pop();
                    if(!stack.isEmpty()){
                        int width = Math.min(height[i],height[stack.peek()]) - height[mid];
                        int length = i - stack.peek() - 1; //这里不能写i-mid
                        sum += width*length;
                    }
                }
                stack.push(i);
            }
        }
        return sum;
    }

    /**
     * 法二：动态规划
     * 将每个位置的左右最高高度分别保存在两个数组中
     */
    public int trap2(int[] height) {
        int[] leftHeight = new int[height.length];
        int[] rightHeight = new int[height.length];
        int result = 0;
        for (int i = 1; i < height.length; i++) {
            leftHeight[i] = Math.max(leftHeight[i - 1], height[i - 1]);
        }
        for (int i = height.length-2; i >=0; i--) {
            rightHeight[i] = Math.max(rightHeight[i + 1], height[i + 1]);
        }
        for (int i = 0; i < height.length; i++) {
            if (i == 0 || i == height.length - 1) {
                continue;
            }
            int item = Math.min(leftHeight[i], rightHeight[i]) - height[i];
            if (item > 0) result += item;
        }
        return result;
    }

    /**
     * 法一：双指针
     * 复杂度较高，因为存在着重复计算
     */
    public int trap1(int[] height) {
        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            if (i == 0 || i == height.length - 1) {
                continue;
            }
            int leftHeight = 0, rightHeight = 0;
            for (int j = 0; j < i; j++) {
                if (height[j] > leftHeight) {
                    leftHeight = height[j];
                }
            }
            for (int j = i + 1; j < height.length; j++) {
                if (height[j] > rightHeight) {
                    rightHeight = height[j];
                }
            }
            int item = Math.min(leftHeight, rightHeight) - height[i];
            if (item > 0) sum += item;
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{4,2,0,3,5,2};
        new Solution42().trap(nums);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
